package com.wushijia.datastructure.tree;

import com.wushijia.datastructure.LinkedQueue;
import com.wushijia.datastructure.LinkedStack;

public class BinaryTree<E> {

  protected BinaryNode<E> root;

  public BinaryTree() {
    root = null;
  }

  public BinaryTree(BinaryNode<E> root) {
    this.root = root;
  }

  public boolean isEmpty() {
    return this.root == null;
  }

  public BinaryNode<E> getRoot() {
    return this.root;
  }

  public void preOrder() {
    System.out.print("\n preOrder is: ");
    preOrder(root);
  }

  private void preOrder(BinaryNode<E> p) {
    if (p != null) {
      System.out.print(p.data + " ");
      preOrder(p.left);
      preOrder(p.right);
    }
  }

  public void inOrder() {
    System.out.print("\n inOrder is: ");
    inOrder(root);
  }

  private void inOrder(BinaryNode<E> p) {
    if (p != null) {
      inOrder(p.left);
      System.out.print(p.data + " ");
      inOrder(p.right);
    }
  }

  public void postOrder() {
    System.out.print("\n postOrder is: ");
    postOrder(root);
  }

  private void postOrder(BinaryNode<E> p) {
    if (p != null) {
      postOrder(p.left);
      postOrder(p.right);
      System.out.print(p.data + " ");
    }
  }

  public int count() {
    return count(root);
  }

  public int count(BinaryNode<E> p) {
    if (p != null) {
      return 1 + count(p.left) + count(p.right);
    } else {
      return 0;
    }
  }

  public int depth() {
    return depth(root);
  }

  public int depth(BinaryNode<E> p) {
    if (p != null) {
      int ld = depth(p.left);
      int rd = depth(p.right);
      return (ld >= rd) ? ld + 1 : rd + 1;
    }
    return 0;
  }

  public BinaryNode<E> search(E value) {
    return search(root, value);
  }

  public BinaryNode<E> search(BinaryNode<E> p, E value) {
    BinaryNode<E> find = null;
    if (p != null && value != null) {
      if (p.data.equals(value)) {
        find = p;
      } else {
        find = search(p.left, value);
        if (find == null) {
          find = search(p.right, value);
        }
      }
    }
    return find;
  }

  public BinaryNode<E> getParent(BinaryNode<E> node) {
    if (root == null || node == null || node == root) {
      return null;
    }
    return getParent(root, node);
  }

  public BinaryNode<E> getParent(BinaryNode<E> p, BinaryNode<E> node) {
    BinaryNode<E> find = null;
    if (p != null) {
      if (p.left == node || p.right == node) {
        find = p;
      } else {
        find = getParent(p.left, node);
        if (find == null) {
          find = getParent(p.right, node);
        }
      }
    }
    return find;
  }


  //6.3.4
  public BinaryTree(E[] preorder) {
    root = create(preorder);
  }

  private int i = 0;

  private BinaryNode<E> create(E[] preorder) {
    BinaryNode<E> p = null;
    if (i < preorder.length) {
      E elem = preorder[i];
      i++;
      if (elem != null) {
        p = new BinaryNode<E>(elem);
        p.left = create(preorder);
        p.right = create(preorder);
      }
    }
    return p;
  }

  //6.3.5
  public void insert(BinaryNode<E> p, E element, boolean leftChild) {
    if (p != null) {
      BinaryNode<E> q = new BinaryNode<E>(element);
      if (leftChild) {
        q.left = p.left;
        p.left = q;
      } else {
        q.right = p.right;
        p.right = q;
      }
    }
  }

  public void insert(BinaryNode<E> p, E element) {
    insert(p, element, true);
  }

  public void remove(BinaryNode<E> p, boolean leftChild) {
    if (p != null) {
      if (leftChild) {
        p.left = null;
      } else {
        p.right = null;
      }
    }
  }

  public void remove(BinaryNode<E> p) {
    remove(p, true);
  }

  //6.3.6
  public void preOrderTraverse() {
    System.out.print("preOrderTraverse is:  ");
    LinkedStack<BinaryNode<E>> stack = new LinkedStack<BinaryNode<E>>();
    BinaryNode<E> p = this.root;
    while (p != null || !stack.isEmpty()) {
      if (p != null) {
        System.out.print(p.data + " ");
        stack.push(p);
        p = p.left;
      } else {
        p = stack.pop();
        p = p.right;
      }
    }
    System.out.println();
  }

  public void inOrderTraverse() {
    System.out.print("inOrderTraverse is:  ");
    LinkedStack<BinaryNode<E>> stack = new LinkedStack<BinaryNode<E>>();
    BinaryNode<E> p = this.root;
    while (p != null || !stack.isEmpty()) {
      if (p != null) {
        stack.push(p);
        p = p.left;
      } else {
        p = stack.pop();
        System.out.print(p.data + " ");
        p = p.right;
      }
    }
    System.out.println();
  }

  public void levelOrder() {
    LinkedQueue<BinaryNode<E>> que = new LinkedQueue<BinaryNode<E>>();
    BinaryNode<E> p = this.root;
    System.out.print("levelOrder is:  ");
    while (p != null) {
      System.out.print(p.data + " ");
      if (p.left != null) {
        que.enqueue(p.left);
      }
      if (p.right != null) {
        que.enqueue(p.right);
      }
      p = que.dequeue();
    }
    System.out.println();
  }

  public String level(BinaryNode<String> find) {
    // TODO Auto-generated method stub
    return null;
  }


  public int countLeaf() {
    return countLeaf();
  }/*
    //������������Ҷ�ӽ������ķ���(�ݹ�ʵ��)
    public int countLeaf(BinaryNode<E> p)
	{
		//�ڴ˴���Ӵ��� 
	}
    
    //�������p���ڲ�εķ���(�ݹ��ǵݹ����ʵ��)
	public int level(BinaryNode<E> p)
	{
		//�ڴ˴���Ӵ��� 
	} 
	*/
}